//https://leetcode.cn/problems/merge-k-sorted-lists/

//解法1
class Solution {
public:
    struct cmp
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;

        for (auto l : lists)
        {
            if (l) heap.push(l);
        }
        ListNode* ret = new ListNode(0);
        ListNode* tail = ret;
        while (!heap.empty())
        {
            ListNode* top = heap.top();
            heap.pop();
            tail->next = top;
            tail = top;

            if (top->next)
                heap.push(top->next);
        }

        tail = ret->next;
        delete ret;
        return tail;

    }
};

//解法2：分治-->归并
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergesort(lists, 0, lists.size() - 1);

    }

    ListNode* mergesort(vector<ListNode*>& lists, int l, int r)
    {
        if (l > r) return nullptr;
        if (l == r) return lists[l];

        //求中间值
        int mid = (l + r) >> 1;

        //左右两部分先合并链表
        ListNode* l1 = mergesort(lists, l, mid);
        ListNode* l2 = mergesort(lists, mid + 1, r);

        //合并左右两部分的链表
        return listmerge(l1, l2);
    }

    ListNode* listmerge(ListNode* l1, ListNode* l2)
    {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        //合并
        ListNode* ret = new ListNode(0);
        ListNode* tail = ret;
        ListNode* cur1 = l1, * cur2 = l2;
        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                tail->next = cur1;
                tail = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                tail = cur2;
                cur2 = cur2->next;
            }
        }
        while (cur1)
        {
            tail->next = cur1;
            break;
        }
        while (cur2)
        {
            tail->next = cur2;
            break;
        }

        tail = ret->next;
        delete ret;
        return tail;
    }
};